/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let n = height.length;
    let res = 0;

    for (let i = 1; i <= n - 2; i++) {
        let l_max = 0, r_max = 0;
        // 找右边高的柱子
        for (let j = i; j < n; j++) {
            r_max = Math.max(r_max, height[j])
        }

        // 找左边高的柱子
        for (let j = i; j >= 0; j--) {
            l_max = Math.max(l_max, height[j])
        }

        // 如果自己就是最高的话
        // l_max == r_max == height[i]
        res += Math.min(l_max, r_max) - height[i]
    }
    return res;
};

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let n = height.length;
    if (n <= 2) {
        return 0;
    }

    let res = 0;

    // 数组充当备忘录
    let l_max = new Array(n);
    let r_max = new Array(n);

    // 初始化base case
    l_max[0] = height[0];
    r_max[n - 1] = height[n - 1];

    // 从左往右算l_max
    for (let i = 1; i < n; i++) {
        l_max[i] = Math.max(height[i], l_max[i - 1])
    }

    // 从右往左计算r_max
    for (let i = n - 2; i >= 0; i--) {
        r_max[i] = Math.max(height[i], r_max[i + 1])
    }

    // 计算答案
    for (let i = 1; i <= n - 2; i++) {
        res += Math.min(l_max[i], r_max[i]) - height[i];
    }

    return res;
};


var trap = function (height) {
    let n = height.length;
    if (n <= 2) {
        return 0;
    }

    let res = 0;

    let left = 0;
    let right = n - 1;

    let l_max = height[0];
    let r_max = height[n - 1];

    while (left <= right) {
        l_max = Math.max(l_max, height[left]);
        r_max = Math.max(r_max, height[right]);

        // res += min(l_max, r_max) - height[i]
        if (l_max < r_max) {
            res += l_max - height[left];
            left++;
        } else {
            res += r_max - height[right];
            right--;
        }
    }
    return res;
}